1. Field of the Invention
The present invention relates to a data encoding device and a data decoding device.
2. Description of the Related Art
Basic technical concept for data compression may be embodied in Huffman encoding. In Huffman encoding, a letter with large occurrence frequency is assigned a shorter bit-length code. That is, respective letters are assigned individually recognizable codes such that a letter which occurs less frequently is assigned a longer bit-length code. This basic encoding method is described in detail in xe2x80x9cThe Data Compression Book, Second Editionxe2x80x9d (written by M. Nelson, Jean-LoupGailly, translated by Takeshi Ogihara and Suguru Yamaguchi, published by K. K. Toppan, in March 1996) and is not described here.
In Huffman encoding, the data element (a unit for encoding) to code word (the minimum code unit) ratio is 1:1. That is, one data element correlates to one code word, and one code word correlates to one data element. When employing such an encoding method, correlation between a data element and a code word is generally defined in an encoding table.
In encoding utilizing an encoding table, assignment of code words to data elements can be achieved without much trouble when each encoding data in a series of encoding data is covered by a group of the relatively small number of kinds of data elements. However, for a case wherein a relatively large number of types of data elements are necessary to cover a series of encoding data, the assignment may not be easily achieved because any increase in the number of involved data elements leads to an increase of the number of code words which must be assigned, which in turn results in an enlarging the encoding table. For example, the encoding of twenty-six English alphabets (data elements) requires an encoding table which defines twenty-six code words, while encoding fifty Japanese syllabary characters requires an encoding table which defines fifty code words.
Increasing the number of code words also increases the amount of time and effort required to create a compatible encoding table, and the resulting encoding table will be relatively more difficult to install. Moreover, in an encoding method in which an encoding table is attached to encoded data, an enlarged encoding table may adversely affect the data compression rate.
In light of the above, in order to reduce the size of an encoding table without adversely affecting a compression rate, additional bit technology has conventionally been employed in the standard method promoted by the Joint Photographic Experts Group, or JPEG, which is an international standard image encoding method. In the following, an additional bit technology will be described, while referring to JPEG as an example.
Briefly, JPEG is a technology for compressing data by removing high frequency components in spatial frequency components of a pixel value in image data, such as photographs, and relies on the fact that there is only a small difference in a pixel value between adjacent pixels. During a process of compression, image data is segmented into image blocks each consisting of 8xc3x978 pixels, for example, and frequency components in each image block are subjected to discrete cosine transformation, or DCT, to divide them into DC and AC components.
For DC components, a difference between adjacent image blocks is subjected to Huffman encoding. In Huffman encoding, difference values of DC components are put into groups before encoding. That is, a group of difference values is treated as a data element, or a unit of data encoding, and an encoding table defining correlation between each group and a code word is used in Huffman encoding.
Further, for accurate description of a difference value of each DC component (a current difference value), a difference between a current difference value and the minimum difference value (a group minimum value) which is assigned to the concerned group is added as an additional bit to a Huffman code word. The additional bit may be calculated as follows:       For    ⁢          xe2x80x83        ⁢    current    ⁢          xe2x80x83        ⁢    difference    ⁢          xe2x80x83        ⁢    value    ⁢          xe2x80x83        ⁢    smaller    ⁢          xe2x80x83        ⁢    than    ⁢          xe2x80x83        ⁢    0    ⁢          xe2x80x83        ⁢          (               less than         0            )                          (                  additional          ⁢                      xe2x80x83                    ⁢          bit                )            =                        (                      current            ⁢                          xe2x80x83                        ⁢            difference            ⁢                          xe2x80x83                        ⁢            value                    )                -                  xe2x80x83                ⁢                  (                      group            ⁢                          xe2x80x83                        ⁢            minimum            ⁢                          xe2x80x83                        ⁢            value                    )                      ⁢          xe2x80x83            For    ⁢          xe2x80x83        ⁢    current    ⁢          xe2x80x83        ⁢    difference    ⁢          xe2x80x83        ⁢    value    ⁢          xe2x80x83        ⁢    equal    ⁢          xe2x80x83        ⁢    to    ⁢          xe2x80x83        ⁢    or    ⁢          xe2x80x83        ⁢    larger    ⁢          xe2x80x83        ⁢    than    ⁢          xe2x80x83        ⁢    0    ⁢          xe2x80x83        ⁢          (              ≧        0            )                  (              additional        ⁢                  xe2x80x83                ⁢        bit            )        =                  (                  current          ⁢                      xe2x80x83                    ⁢          difference          ⁢                      xe2x80x83                    ⁢          value                )            +              (                  group          ⁢                      xe2x80x83                    ⁢          minimum          ⁢                      xe2x80x83                    ⁢          value                )            ⁢              xe2x80x83            +      M      -      1      
wherein M is the number of types of data present in the group. This calculation, however, is theoretical. In actuality, a simplified version utilizing the characteristics of an encoding table is used.
In decoding, an encoding table which was referred to in encoding is again referred to in order to specify a relevant group based on a Huffman code word. Then, a difference value of the original DC component is obtained based on the group minimum value of the identified group and the additional bit.
As described above, according to an example of a conventional encoding technology, an encoding table using data groups and additional information (additional bit) for specifying particular data in a data group are utilized to ensure a smaller encoding table.
However, although the above-described conventional encoding technology which utilizes an encoding table using data groups and additional information can improve compression efficiency when occurrence frequencies of the respective data which constitute a group are substantially constant, the technology faces a difficulty when occurrence frequencies of the data are not constant. Problems often arise because improvement of compression efficiency in the latter case requires enlarging the size of the encoding table, and an enlarged coding table is more difficult to install.
In short, in a technology such as JPEG, in which values are grouped, even when it may be possible to handle situations wherein successive values are put into a single group, a situation wherein discrete values are placed in one group may face difficulty. That is, because it is expected in JPEG that a difference value of each DC component will be substantially zero, based on the assumption that a difference in pixel values of adjacent pixels is small, values which are closer to zero may have larger occurrence frequencies, and therefore should be assigned a shorter code word. In such a case, grouping may be possible such that values equal to or smaller than 3 be assigned the shortest code word. However, should values xe2x80x9c0.8 to 1.2xe2x80x9d have smaller frequency, the values may better e grouped into xe2x80x9c0 to 0.8xe2x80x9d, xe2x80x9c0.8 to 1.2xe2x80x9d, and xe2x80x9c1.2 to 3xe2x80x9d to attain h compression efficiency.
That is, presence of a peculiar value range, such as a value range without successiveness in terms of occurrence frequency or with difficulty in estimation of occurrence frequency, results in a need for increasing the number of data groups and thus entries to an encoding table. Creation and installation of such an enlarged encoding table are difficult to achieve.
The present invention was conceived in view of the above, and the present invention therefore advantageously provides an improved data encoding device and an improved data decoding device.
According to one aspect of the present invention, there is provided a data encoding device, comprising an encoding table for correlating a data element with a code word such that one data element is correlated with N number of code words and one code word is correlated with one data element, the data element serving as a unit of data encoding, N being an integer larger than zero; a retrieve unit for determining a data element corresponding to each of a series of encoding data and for retrieving the N number of code words correlated with the determined data element with reference to the encoding table; a selector for selecting one code word from among the N number of code words according to predetermined criteria; and a generator for generating, as required, additional information which specifies encoding data correlated with the selected code word among one or more encoding data corresponding to the determined data element correlated with the selected code word, whereby each encoding data is converted into either additional information attached encoded data or normal encoded data, the additional information attached encoded data consisting of a code word and additional information, the normal encoded data consisting of a code word.
According to another aspect of the present invention, there is provided a data encoding device, comprising encoding tables each for correlating one data element with one code word, the data element serving as a unit of data encoding; a retrieve unit for determining a data element corresponding to each of a series of encoding data and for retrieving N number of encoding tables which each define a code word correlated with the determined data element, N being an integer larger than zero; a selector for selecting one encoding table from among the N number of encoding tables according to predetermined criteria to output a code word which is defined by the selected encoding table as correlated with the determined data element; a generator for generating, as required, additional information which specifies encoding data correlated with the selected code word among one or more encoding data corresponding to the determined data element correlated with the selected code word, whereby each encoding data is converted into either additional information attached encoded data or normal encoded data, the additional information attached encoded data consisting of a code word and additional information, the normal encoded data consisting of a code word.
In the above, the predetermined condition may define such that selection means selects the shortest code word among the N number or code word or one code word according to a predetermined priority order.
It is preferable, when selecting one encoding table from among two or more encoding tables, that the selection means outputs selection information which specifies the selected encoding data, for correlation with each code word.
According to still another aspect of the present invention, there is provided a data decoding device, comprising an encoding table for correlating a data element with a code word such that one data element is correlated with N number of code words and one code word is correlated with one data element, the data element serving as a unit of data encoding, N being an integer larger than zero; a retrieve unit for sequentially extracting encoded data from a series of encoded data obtained by a data encoding device and for retrieving a data element correlated with a code word contained in the extracted encoded data with reference to the encoding table; and a decoder for decoding, when the extracted encoded data is additional information attached encoded data, additional information based on the retrieved data element and the extracted additional information.
According to yet aspect of the present invention, there is provided a data decoding device, comprising encoding tables each for correlating one data element with a code word, the data element serving as a unit of data encoding; a retrieve unit for sequentially extracting encoded data from a series of encoded data obtained by a data encoding device which comprises the encoding tables, and for retrieving a data element correlated with a code word contained in the extracted encoded data with reference to the encoding table; and a decoder for decoding, when the extracted encoded data is additional information attached encoded data, additional information based on the retrieved data element and the extracted additional information.
According to yet aspect of the present invention, there is provided a data decoding device, comprising encoding tables each for correlating one data element with a code word, the data element serving as a unit of data encoding; a retrieve unit for sequentially extracting encoded data from a series of encoded data obtained by a data encoding device which comprises the encoding tables and outputs selection information concerning the selected encoding table, to extract a code word contained in the extracted encoded data, for selecting one encoding table from among the encoding tables based on selection information which is correlated with the extracted code word, and for retrieving a data element correlated with the extracted code word with reference to the selected encoding table; and decoder for decoding, when the extracted encoded data is additional information attached encoded data, additional information based on the determined data element and the extracted additional information.
According to yet aspect of the present invention, there is provided a data encoding method employing an encoding table which correlates a data element with code word such that one data element is correlated with N number of code words and one code word is correlated with one data element, the data element serving as a unit of data encoding, N being an integer larger than zero; the method comprising a search step of determining a data element corresponding to each of a series of encoding data to determine the N number of code words correlated with the determined data element with reference to the encoding table; a selection step of selecting one code word from among the N number of code words according to a predetermined criteria; and a generation step of generating, as required, additional information which specifies encoding data correlated with the selected code word among one or more encoding data corresponding to the determined data element correlated with the selected code word, whereby each encoding data is converted into either additional information attached encoded data or normal encoded data, the additional information attached encoded data consisting of a code word and additional information, the normal encoded data consisting of a code word.
According to yet aspect of the present invention, there is provided encoded data generated by the above-described data encoding method.
According to yet aspect of the present invention, there is provided a data decoding method employing a table which correlates a data element with a code word such that one data element is correlated with N number of code words and one code word is correlated with one data element, the data element serving as a unit of data encoding, N being an integer larger than zero, the method, comprising: a search step of sequentially extracting encoded data from a series of encoded data obtained by a data encoding device and determining a data element correlated with a code word contained in the extracted encoded data with reference to the table; and a decoding step of decoding, when the extracted encoded data is additional information attached encoded data, additional information based on the determined data element and the extracted additional information.
According to yet aspect of the present invention, there is provided encoded data generated by encoding a series of encoding data, including additional information attached encoded data and normal encoded data, the additional information attached encoded data consisting of a code word and additional information and the word data consisting of a code word.
According to yet aspect of the present invention, there is provided encoded data, generated using two or more encoding tables which respectively correlate one data element with different code words, the data element serving as a unit of data encoding, as the product of a search step of determining a data element corresponding to each of a series of encoding data and determining N number of encoding tables which each define a code word correlated with the determined data element, N being an integer larger than zero; a selection step of selecting one encoding table from among the N number of encoding tables according to a predetermined criteria to output a code word correlated with the determined data element according to the selected encoding table; a generation step of generating, as required, additional information which specifies encoding data correlated with the selected code word among one or more encoding data corresponding to the determined data element correlated with the selected code word, to thereby convert each encoding data into either additional information attached encoded data or normal encoded data, the additional information attached encoded data consisting of a code word and additional information, the normal encoded data consisting of a code word, wherein the encoded data contains at least one additional information attached encoded data and one normal encoded data according to the series of encoding data.
According to yet aspect of the present invention, there is provided encoded data according to claim 15, further containing information specifying an encoding table which is selected when outputting each code word.